package com.algorithm.learning.base.图;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/29 21:22
 **/
public class 图的深度优先遍历 {

    /**
     * 深度优先遍历：如果需要快速探索图的结构或检测环路，DFS可能是更合适的方法。
     *
     * 1、访问顺序：从起始节点开始，沿着图的边尽可能深的搜索树的分支，如果遇到一个节点没有子节点或者子节点已经被访问了，则回到上一个节点继续探索未访问的分支
     * 2、通常用Stack实现
     * 3、应用场景：拓扑排序、检测图中的环路。寻找路径
     * 4.特点：可以尽早的发现长路径，但对于寻找最短路径并不是最优选择。
     *
     *  @see 图的宽度优先遍历#bfs(Node)
     * @param node
     */
    public static void dfs(Node node) {
        if (node == null) {
            return;
        }
        // 这个栈，其实记录的是深度优先遍历的路径
        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();
        stack.add(node);
        set.add(node);
        // 这里要注意，要在弹出前，打印节点
        System.out.println(node.value);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            for (Node next : node.nexts) {
                if (!set.contains(next)) {
                    // 这里把当前点重新压入栈
                    stack.push(cur);
                    // 再把next点压入栈
                    stack.push(next);
                    // 把next点加入set，防止重复遍历
                    set.add(next);
                    System.out.println(next.value);
                    // 直接break了，不在遍历了
                    break;
                }
            }
        }
    }
}
